﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FindGreatestLinkedNode.Question;
using System.Collections;

namespace FindGreatestLinkedNode.Answer
{
    class Jimson : IFindNearestGreatestNodeInBinaryTree
    {
        static int? ree = null;
        public int? FindNearestGreatestNode(Node root, int k)
        {
            //int? parentData = null;
            //int? leftData = null;
            //int? rightData = null;           

            int? res = findNode(root, k, null,  null,  null);


            return ree;
        }

        private int? findNode(Node root, int data, int? pd,  int? ld,  int? rd)
        {
            int? res = null;
            if (data == root.Data)
            {
                if (null == root.LeftChild)
                {
                    ld = null;
                }
                else
                {
                    ld = root.LeftChild.Data;
                }

                if (null == root.RightChild) { rd = null; } else rd = root.RightChild.Data;

                ArrayList arr = new ArrayList();
                arr.Add(pd); arr.Add(data); arr.Add(ld); arr.Add(rd);
                arr.Sort();
                ree = arr[3] as int?;
                return res;              
            }
            else
            {
                int?  res1 = null ;int? res2 = null;
                if (root.LeftChild != null )
                {
                     res1 = findNode(root.LeftChild, data, root.Data, ld, rd);
                }

                if (root.RightChild != null )
                {
                    
                     res2 =  findNode(root.RightChild, data, root.Data, ld, rd);
                }

                if (res1 != null || res2 != null)
                {
                    if (res2 == null)
                        return res1.Value;
                    if (res1 == null)
                        return res2.Value;
                    return res1.Value >= res2.Value ? res1.Value : res2.Value;
                }
                return null;
            }
           
        }
    }
}
